import java.util.Deque;
import java.util.ArrayDeque;
/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 86186
 * Date: 2023-10-28
 * Time: 10:47
 */
public class Test {
    public boolean backspaceCompare(String s, String t) {
        return StringEquals(s).equals(StringEquals(t));
    }

    private String StringEquals(String s) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            if (ch == '#') {
                if (sb.length() != 0) {
                    sb.deleteCharAt(sb.length() - 1);
                }
            }else {
                sb.append(ch);
            }
        }

        return sb.toString();
    }

    public int calculate(String s) {
        //整体做题思路：创建一个栈，栈中存放的都是运算过后的数字，到最后的时候只需将栈中的数据相加就可以了
        //用一个变量op来记录遇到的运算符，op初始化为+，当遇到数字的时候，如果此时op是+，那么该数字直接进栈
        //如果此时op是-的话，将-tmp放入栈；如果是*或者/的话，就从栈中取出一个元素与当前数字进行*、/运算
        Deque<Integer> deque = new ArrayDeque<>();
        int i = 0;
        char op = '+';
        while (i < s.length()) {
            char ch = s.charAt(i);
            if (ch == ' ') i++;
            else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') {
                op = ch;
                i++;
            }
            else {
                int tmp = 0;
                while (i < s.length() && (s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
                    tmp = tmp * 10 + (s.charAt(i) - '0');
                    i++;
                }
                if (op == '+') {
                    deque.offer(tmp);
                }else if(op == '-') {
                    deque.offer(-tmp);
                }else if (op == '*') {
                    deque.offer(deque.poll() * tmp);
                }else {
                    deque.offer(deque.poll() / tmp);
                }
            }
        }
        int ret = 0;
        while (!deque.isEmpty()) {
            ret += deque.poll();
        }

        return ret;
    }

    public String decodeString(String s) {
        Deque<StringBuilder> d1 = new ArrayDeque<>();
        Deque<Integer> d2 = new ArrayDeque<>();
        d1.push(new StringBuilder());
        int i = 0, n = s.length();
        while (i < n) {
            char ch = s.charAt(i);
            if (ch >= '0' && ch <= '9') {
                int tmp = 0;
                while (i < n && (s.charAt(i) >= '0' && s.charAt(i) <= '9')) {
                    tmp = tmp * 10 + (s.charAt(i) - '0');
                    i++;
                }
                d2.push(tmp);
            }else if (ch == '[') {
                i++;
                StringBuilder sb = new StringBuilder();
                while (i < s.length() && (s.charAt(i) >= 'a' && s.charAt(i) <= 'z')) {
                    sb.append(s.charAt(i));
                    i++;
                }
                d1.push(sb);
            }else if (ch == ']'){
                int k = d2.pop();
                StringBuilder tmp = d1.pop();
                while (k-- != 0) {
                    d1.peek().append(tmp);
                }
                i++;
            }else {
                StringBuilder tmp = new StringBuilder();
                while (i < n && (s.charAt(i) >= 'a' && s.charAt(i) <= 'z')) {
                    tmp.append(s.charAt(i));
                    i++;
                }
                d1.peek().append(tmp);
            }
        }
        return d1.peek().toString();
    }
}
